package Lee_code;

import java.util.Arrays;

/**
 * @author blh
 * @date 2024年07月05日 17:42
 */
public class Lee_79_75 {
    int m;
    int n;
    String target;
    Boolean res;

    public boolean exist(char[][] board, String word) {
        target = word;
        m = board.length;
        n = board[0].length;
        res = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)) {
                    Boolean[][] seen = new Boolean[m][n];
                    for (Boolean[] booleans : seen) {
                        Arrays.fill(booleans, false);
                    }
                    dfs(i, j, seen, new StringBuilder(), board);
                    if (res){
                        return res;
                    }
                }
            }
        }
        return res;
    }

    private void dfs(int i, int j, Boolean[][] seen, StringBuilder sb, char[][] board) {
        if (i >= 0 && i <= m - 1 && j >= 0 && j <= n - 1 && !seen[i][j]) {
            if (target.charAt(sb.length()) != board[i][j]) {
                return;
            }
            Boolean[][] tempSeen = new Boolean[m][n];
            for (int k = 0; k < m; k++) {
                System.arraycopy(seen[k], 0, tempSeen[k], 0, n);
            }
            sb.append(board[i][j]);
            tempSeen[i][j] = true;
            if (sb.toString().equals(target)) {
                res = true;
                return;
            }
            dfs(i + 1, j, tempSeen, new StringBuilder(sb), board);
            dfs(i - 1, j, tempSeen, new StringBuilder(sb), board);
            dfs(i, j + 1, tempSeen, new StringBuilder(sb), board);
            dfs(i, j - 1, tempSeen, new StringBuilder(sb), board);
        }
    }


}
